Low-density parity-check (LDPC) codes have recently been the subject of increased research interest for their enhanced performance on additive white Gaussian noise (AWGN) channels. As described by Shannon's Channel Coding Theorem, the best performance is achieved when using a code consisting off very long codewords. In practice, codeword size is limited in the interest of reducing complexity, buffering, and delays. LDPC codes are block codes, as opposed to trellis codes that are built on convolutional codes. LDPC codes constitute a large family of codes including turbo codes. Block codewords are generated by multiplying (modulo 2) binary information words with a binary matrix generator. LDPC codes use a check parity matrix H, which is used for decoding. The term low density derives from the characteristic that the check parity matrix has a very low density of non-zero values, making it a relatively low complexity decoder while retaining good error protection properties.
The parity check matrix H measures (N−K)×N, wherein N represents the number of elements in a codeword and K represents the number of information elements in the codeword. The matrix H is also termed the LDPC mother code. For the specific example of a binary alphabet, N is the number of bits in the codeword and K is the number of information bits contained in the codeword for transmission over a wireless or a wired communication network or system. The number of information elements is therefore less than the number of codeword elements, so K<N. FIGS. 1a and 1b graphically describe an LDPC code. The parity check matrix 10 of FIG. 1a is an example of a commonly used 512×4608 matrix, wherein each matrix column 12 corresponds to a codeword element (variable node of FIG. 1b) and each matrix row 14 corresponds to a parity check equation (check node of FIG. 1b). If each column of the matrix H includes exactly the same number m of non-zero elements, and each row of the matrix H includes exactly the same number k of non-zero elements, the matrix represents what is termed a regular LDPC code. If the code allows for non-uniform counts of non-zero elements among the columns and/or rows, it is termed an irregular LDPC code.
Irregular LDPC codes have been shown to significantly outperform regular LDPC codes, which has generated renewed interest in this coding system since its inception decades ago. The bipartite graph of FIG. 1b illustrates that each codeword element (variable nodes 16) is connected only to parity check equations (check nodes 18) and not directly to other codeword elements (and vice versa). Each connection, termed a variable edge 20 or a check edge 22 (each edge represented by a line in FIG. 1b), connects a variable node to a check node and represents a non-zero element in the parity check matrix H. The number of variable edges connected to a particular variable node 16 is termed its degree, and the number of variable degrees 24 are shown corresponding to the number of variable edges emanating from each variable node. Similarly, the number of check edges connected to a particular check node is termed its degree, and the number of check degrees 26 are shown corresponding to the number of check edges 22 emanating from each check node. Since the degree (variable, check) represents non-zero elements of the matrix H, the bipartite graph of FIG. 1b represents an irregular LDPC code matrix. The following discussion is directed toward irregular LDPC codes since they are more complex and potentially more useful, but may also be applied to regular LDPC codes with normal skill in the art.
Irregular codes can be designed for many different symmetric channels via density evolution and genetic hill-climbing algorithms (i.e., Differential Evolution) by adjusting variable edge polynomial λ(x) and check edge polynomial ρ(x), defined as:
      λ    ⁡          (      x      )        =                    ∑                  i          =          2                          d          l                    ⁢                        λ          i                ⁢                  x                      i            -            1                          ⁢                                  ⁢        and        ⁢                                  ⁢                  ρ          ⁡                      (            x            )                                =                  ∑                  i          =          2                          d          r                    ⁢                        ρ          i                ⁢                  x                      i            -            1                              where {λ2, λ3, . . . λdi} and {ρ2, ρ3, . . . ρdr} represent the edge distributions indicating the fraction of edges 20, 22 connected to variable and check nodes of degrees {2, 3, . . . dl} and {2, 3, . . . dr}, respectively, out of the total number of edges. The edge distributions determine the asymptotic performance of the code ensemble, the code rate of the ensemble, and any code realizations derived from the distributions.
In accordance with various conventional systems implementing an LDPC coding architecture including multiple coding rates for its error control, an LDPC encoder encodes a K-dimensional sequence of information bits into an N-dimensional codeword by accessing a stored LDPC mothercode and one of several stored puncture sequences, one puncture sequence corresponding to one code rate. As will be appreciated, however, such conventional systems may require significant non-volatile memory for each coding rate for a single mother code. In this regard, in one conventional system, a different LDPC code is designated for each coding rate and channel (i.e., different code realizations from different λ(x) and ρ(x) corresponding to the desired code rates). Such a conventional system uses one LDPC code for each coding rate, and may increase substantially when the set of code rates is large and/or when code words are long. The memory requirements can render this approach prohibitive for adaptive coding and modulation schemes operating in slowly varying channels. In another conventional system, codeword elements of a single LDPC code are punctured using multiple puncturing sequences chosen at random using puncturing probabilities. This system requires memory for storing multiple puncturing sequences, one for each code rate, which may become prohibitive for a large set of coding rates and/or long codeword lengths.
Besides the substantial amount of memory that may be required to store conventional puncturing sequences for various coding rates, the determination of the puncturing sequences may itself be computationally intensive. In this regard, one conventional technique for designing a puncture sequence is based on linear programming to determine puncturing probabilities that maximize the puncturing fraction:
      p          (      0      )        =            ∑              j        =        2                    d        l              ⁢                  λ        j        ′            ⁢              π        j                  (          0          )                    for a given signal to noise ratio (SNR, or bit/symbol energy to noise power spectral density Eb/N0) threshold, where λ′j represents the fraction of variable nodes 16 of degree j. In another conventional technique, a puncture sequence is designed based on differential evaluation based on Density Evolution, which may be somewhat more complex than the linear programming technique with near identical results. Each of these techniques for designing the puncture sequences are very computationally expensive, and their resulting sequences themselves require so much memory as to be potentially prohibitive for an adaptive coding system.